1. Field of the Invention
The present invention relates to real-time event scheduling systems. In particular, the invention relates to dynamic slip control that takes into account the actual time that events occur.
2. Description of the Related Art
Real-time systems must maintain a timely and accurate interaction with their physical environment in order to meet the overall system design objectives. The times at which the interaction occurs and the values of the system state at the interaction times are critical parts of the system performance. The further the actual interaction time is from the desired interaction time, and the further the system state value is from the desired value, the worse is the quality of the system performance.
The interaction between the real-time system and its environment may be initiated by the real-time system, which is called proactive interaction, or by the environment, which is called reactive interaction. Since the real-time system and its environment are typically distributed systems, their interactions are asynchronous.
When elapsed time does not play a role in the interaction, the situation requires discrete event scheduling only. However, when elapsed time does play a role in the interaction, the situation requires real-time event scheduling. Discrete event scheduling is usually adequate when the real-time system's internal state is purely logical or symbolic. Real-time event scheduling is necessary when the real-time system has time-dependent internal state. Some examples of systems where real-time event scheduling is necessary are observer-based control systems, discrete time observation feedback systems, and real-time simulation systems. In the first case, the real-time system filters its timed observations of the environment. In the second case, the real-time system uses timers to schedule the observation feedback computations. In the third case, the real-time system simulates the control system as well as parts or all of the physical environment.
In many implementations, real-time systems are realized simply as discrete time tasks with periodic scheduling. For example, let x be the real-time system's internal state and let Δ be the scheduling period. The variable k denotes the period number and the function ck updates the internal state to the new period number. Then, at times0,Δ,2Δ, . . . , kΔ,the computationx[k+1]=ck(x[k])is performed based on the observation at kΔ.
Often, multiple such tasks are scheduled concurrently on the same real-time implementation platform, and techniques such as rate monotonic scheduling are used to guarantee the design performance of such systems. Exemplary references include C. L. Liu and J. W. Layland, Scheduling algorithms for multiprogramming in a hard real-time environment, 20(1) JOURNAL OF ACM 46-61 (January 1973); J. Y.-T. Leung and M. L. Merrill, A note on preemptive scheduling of periodic, real-time tasks, 11(3) INFORMATION PROCESSING LETTERS 115-118 (November 1980); J. Y.-T. Leung and J. Whitehead, On the complexity of fixed-priority scheduling of periodic, real-time tasks. 2 PERFORMANCE EVALUATION 237-250 (1982); D. W. Leinbaugh, Guaranteed response time in a hard real-time environment, IEEE TRANSACTIONS ON SOFTWARE ENGINEERING (January 1980); S.-C. Cheng, J. A. Stankovic, and K. Ramamritham, Scheduling algorithms for hard real-time systems—a brief survey, IEEE TUTORIAL HARD REAL-TIME SYSTEMS 150-173 (1988); J. Lehoczky, L. Sha, and Y. Dine, The rate monotonic scheduling algorithm: Exact characterization and average case behavior, PROCEEDINGS OF THE REAL-TIME SYSTEMS SYMPOSIUM 166-171 (December 1989). However, this design guarantee may not extend to the implementation of the actual system.
Because many real-time platforms may be implemented with periodic scheduling, such an approach is simple and attractive for scheduling each task. However, the periodic scheduling approach, while simple, leads to several drawbacks when implementing event scheduling models.
First, the essential asynchronous nature of the system is lost, leading to added latency in the interaction with the environment. In proactive interactions, this latency arises because the interaction time is different from the desired event time, which is typically the time at which the system's internal state crosses some guard condition. In reactive interactions, this latency arises because the interaction occurs at the end of the scheduled period even though the asynchronous interrupt may occur before the period expires.
Second, additional computational load is placed on the implementation because computations are performed periodically whether or not they are used. This additional computational load may require more expensive real-time implementation platforms.
Third, while the kth event is scheduled at time kΔ, the actual time at which the event occurs is generally off from the scheduled time because of the nonideal nature of the underlying physical implementation platform. Even so, the state value at the scheduled time kΔ, and not the state value at the actual event time, is used in the interaction. This leads to inaccurate interaction with the physical environment.
Given these problems, real-time event scheduling is often desired over event scheduling implemented by a periodic system. However, even if a well-designed real-time system can theoretically guarantee the timely completion of all tasks, in practice the tasks may not be completed at the desired times because of imperfections in the underlying real-time implementation platform.
The discrepancy between the actual and desired interaction times is called the slip of the system. Slip control is an algorithmic technique for ensuring that slip is small. Dynamic slip control uses the application's dynamical model information to reduce both slip and the discrepancy in the system's state values.
Traditional real-time scheduling techniques typically do not use the application's dynamical models for fine-tuning the scheduler performance. While system implementations may use physical time information for scheduling timer interrupts, they do not use physical time information to correct for slip. Thus, while they can achieve some level of slip control for simple applications with periodic schedules, generally they cannot achieve dynamic slip control for general purpose real-time event scheduling. Thus, there is a need for an algorithmic technique for dynamic slip control for real-time event scheduling.